package 算法.leetcode.offer;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author lchenglong
 * @date 2022/4/21
 */
public class Offer38 {

    public static void main(String[] args) {
        Offer38 instance = new Offer38();
        String[] ans = instance.permutation("aab");
        System.out.println(Arrays.toString(ans));
    }

    Set<String> ans ;
    public String[] permutation(String s) {
        ans = new HashSet<String>();
        char[] list = s.toCharArray();
        int m = s.length()-1;
        Perm(list, 0, m);
        return ans.toArray(new String[ans.size()]);
    }

     void Perm(char[] list, int k, int m) {
        //list 数组存放排列的数，K表示层 代表第几个数，m表示数组的长度
        if (k == m) {
            //K==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= m; i++)
                sb.append(list[i]);
            ans.add(sb.toString());

        } else {
            for (int i = k; i <= m; i++) {
                swap(list, i, k);
                Perm(list, k + 1, m);
                // 回溯
                swap(list, i, k);
            }
        }

    }

    void swap(char[] list, int i, int j) {
        char tmp;
        tmp = list[i];
        list[i] = list[j];
        list[j] = tmp;
    }
}
